45. 跳跃游戏 II

Similar Question

Solution Tips

方案一: 贪心

var jump = function(nums) {
    // 这次也是倒过来, 找到最远的能覆盖 last 的 index, 就跳到那就行
    // 只保留最大的 cover 就行, 小的就不要走了
    // 在能跳的范围内, 要去跳下一个位置能跳的最远的
    // 那就是在能跳的范围内, 再找一个最大值
    const n = nums.length;
    if (n === 1) return 0;
    let step = 1;
    let start = 0;
    while (start < nums.length) {
        const end = start + nums[start];
        if (end > n - 1) {
            return step;
        }
        // 找到 start 到 end 间的最大值
        let nextStep = 0;
        let curMax = 0;
        for (let i = start; i <= end; i++) {
            if (i + nums[i] > curMax) {
                curMax = i + nums[i];
                nextStep = i;
            }
        }
        start = nextStep;
        step++;
        if (curMax >= n - 1) {
            return step;
        }

    }
    return step;
};

console.log(jump([7,0,9,6,9,6,1,7,9,0,1,2,9,0,3]))

方案二: 贪心优化

每次跳完之后更新 index ,其实可以直接更新为上一次的 end

在 nextStep 到 end 之间的元素, 已经遍历过一次了, 他们的跳动范围小于 nextStep

function greedyOptimization(nums){
    /**
     * 如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
     * 我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳
     * 跃次数增加 1。在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界
     * 一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后
     * 一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
     */

    // 初始化当前能够到达的最大下标为0
    let maxPosition=0,
    // 初始化边界为0
        end=0,
    // 初始化步数为0    
        step=0;
    // 从左向右遍历数组
    for(let i=0;i<nums.length-1;i++)
    {
        // 重新赋值计算当前能够到达的最大下标
        maxPosition=Math.max(maxPosition,nums[i]+i);
        // 到达边界
        if(i===end)
        {
            // 更新边界为能到达最大下标
            end=maxPosition;
            // 步数增加1
            step++;
        }
    }
    // 返回结果
    return step;
}